package com.ycy.sort;

import org.junit.Test;

import java.util.Arrays;

public class QuickSortDemo3 {

  @Test
  public void test() {

//    for (int i = 0; i < 10; i++) {
//      this.arr = Utils.RandomArr(3);
//      System.out.println(Arrays.toString(this.arr));
//      quickSort(0, 2);
//      System.out.println(Arrays.toString(this.arr));
//      System.out.println();
//    }

//    for (int i = 0; i < 10; i++) {
//      this.arr = Utils.RandomArr(4);
//      System.out.println(Arrays.toString(this.arr));
//      sort(0, 3);
//      System.out.println(Arrays.toString(this.arr));
//      System.out.println();
//    }


    this.arr = new int[]{72, 37, 20, 13};
    System.out.println(Arrays.toString(this.arr));
    sort(0, 3);
    System.out.println(Arrays.toString(this.arr));

  }


  public void sort(int low, int high) {

    if (low >= high) return;

    int i = quickSort(low, high);


    sort(low, i - 1);
    sort(i + 1, high);
  }

  int[] arr;

  public int quickSort(int low, int high) {

    if (low >= high) return 0;

    //
    int base = this.arr[low];

    int lowIndex = low;
    int highIndex = high;

    while (lowIndex < highIndex) {
//      if (lowIndex >= highIndex) {
//        break;
//      }
//      for (int i = lowIndex; i < high + 1; i++) {
//        if (this.arr[i] > base) break;
//        lowIndex++;
//      }
//      for (int i = highIndex; i >= low; i--) {
//        if (this.arr[i] < base) break;
//        highIndex--;
//      }
      while (this.arr[lowIndex] <= base && lowIndex < high)
        lowIndex++;

      while (base < this.arr[highIndex] && low < highIndex) {
        highIndex--;
      }

      if (lowIndex < highIndex)
        exchange(highIndex, lowIndex);
    }

    //base ，highindex exchange
//    if (highIndex != low) {
//      exchange(highIndex, low);
//    }
    exchange(low, highIndex);
    return highIndex;
  }

  public void exchange(int i, int j) {
//    if (i >= j) return;
    int tmp = this.arr[i];
    this.arr[i] = this.arr[j];
    this.arr[j] = tmp;
  }


}
